// ml:run = $bin < input
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <iostream>
#include <algorithm>

int const maxn = 400005;
int lson[maxn*30],rson[maxn*30],c[maxn*30],T[maxn];
int a[maxn],b[maxn],len,tot,vis[maxn];
int n, m;

void hase(int k)
{
    std::sort(b,b+k);
    len = std::unique(b,b+k) - b;
}

int get_hase(int k)
{
    return (std::lower_bound(b,b+len,k) - b);
}

int build(int l,int r)
{
    int root = tot++;
    c[root] = 0;
    if(l != r)
    {
        int mid = (l +r) >> 1;
        lson[root] = build(l,mid);
        rson[root] = build(mid + 1,r);
    }
    return root;
}

int insert1(int root,int pos,int val)
{
    int newroot = tot++;
    int tmp = newroot;
    c[newroot] = c[root] + val;
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(pos <= mid)
        {
            lson[newroot] = tot++;
            rson[newroot] = rson[root];
            newroot = lson[newroot];
            root = lson[root];
            r = mid;
        }
        else
        {
            lson[newroot] = lson[root];
            rson[newroot] = tot++;
            newroot = rson[newroot];
            root = rson[root];
            l = mid +1;
        }
        c[newroot] = c[root] + val;
    }
    return tmp;
}

int A,B;
int tans = 0;

int query(int root,int l, int r)
{
    if(A<= l && r <= B)
    {
        return c[root];
    }
    int mid = (l + r) >> 1;
    int ans = 0;
    if(A <= mid) ans += query(lson[root],l,mid);
    if(B > mid) ans += query(rson[root],mid + 1, r);
    return ans;
}

int query2(int root, int l, int r, int kth)
{
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int ans = 0;
    if(A <= mid) ans += query(lson[root],l,mid);

    if (ans >= kth) return query2(lson[root], l, mid, kth);
    /* if(B > mid) ans += query(rson[root],mid + 1, r); */
    return query2(rson[root], mid + 1, r, kth - ans);
}

int calc(int w)
{
    B = n;
    int k = query(T[w], 1, n);
    /* printf("->%d\n", k); */
    k = k - (k + 1) / 2;
    if (!k) return A;
    k++;
    /* printf("->%d\n", k); */
    return query2(T[w], 1, n, k);
    int l = A, r = w;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        B = mid;
        if (query(T[w], 1, n) <= k) l = mid;
        else r = mid;
    }
    B = r;
    if (query(T[w], 1, n) == k) l = r;
    /* printf("->%d\n", l); */
    return l + 1;
}

int main()
{
    int tcase; scanf("%d", &tcase);
    for (int ti = 1; ti <= tcase; ti++) {
        printf("Case #%d:", ti);
        scanf("%d%d", &n, &m);
        len = tot = 0;
        memset(vis,-1,sizeof(vis));
        int i;
        for(i = 1; i <= n; i++)
        {
            scanf("%d",&a[n - i + 1]);
            b[len++] = a[n - i + 1];
        }
        hase(len);
        T[0] = build(1,n);
        for(i = 1;i <= n; i++) {
            int tmp = T[i-1];
            int vv = get_hase(a[i]);
            if(vis[vv] != -1) {
                tmp = insert1(T[i-1],vis[vv],-1);
            }
            T[i] = insert1(tmp,i,1);
            vis[vv] = i;
        }
        int ans = 0;
        while (m--) {
            int w, l, r;
            scanf("%d %d",&l,&r);
            w = std::min(((l + ans) % n) + 1, ((r + ans) % n) + 1);
            A = std::max(((l + ans) % n) + 1, ((r + ans) % n) + 1);
            w = n - w + 1;
            A = n - A + 1;
            /* printf("\ninterval %d %d\n", A, w); */
            ans = calc(w);
            ans = n - ans + 1;
            printf(" %d", ans);
        }
        printf("\n");
    }
}

